package simple;

import data.TreeNode;
import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/8/8 22:32
 */
public class No257_二叉树的所有路径 {
    public static void main(String[] args) {
        Solution257 solution257 = new Solution257();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(7);
        root.left.right = new TreeNode(4);
        root.left.right.left = new TreeNode(3);
        root.left.right.right = new TreeNode(5);
        root.right = new TreeNode(8);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        List<String> list = solution257.binaryTreePaths(root);
        System.out.println();
    }
}

class Solution257 {
    public List<String> binaryTreePaths(TreeNode root) {
        //迭代法 BFS
        //No104_2 二叉树的深度
        //(树,路径)
        Stack<Pair<TreeNode, String>> stack = new Stack<>();
        stack.push(new Pair<>(root, ""));
        List<String> res = new ArrayList<>();
        while (!stack.isEmpty()) {
            Pair<TreeNode, String> pop = stack.pop();
            TreeNode checkTree = pop.getKey();
            String checkPath = pop.getValue();
            if (checkTree != null) {
                checkPath = checkPath + checkTree.val;
                if (checkTree.left == null && checkTree.right == null) {
                    //说明是叶子节点
                    res.add(checkPath);
                    continue;
                }
                //说明有"递归"
                checkPath = checkPath + "->";
                if (checkTree.left != null && checkTree.right != null) {
                    //说明有2个子节点
                    stack.push(new Pair<>(checkTree.left, checkPath));
                    stack.push(new Pair<>(checkTree.right, checkPath));
                } else if (checkTree.left == null) {
                    //只有右节点
                    stack.push(new Pair<>(checkTree.right, checkPath));
                } else if (checkTree.right == null) {
                    //只有左节点
                    stack.push(new Pair<>(checkTree.left, checkPath));
                }
            } else {
                continue;
            }
        }
        return res;
    }
}



    //public List<String> binaryTreePaths(TreeNode root) {
    //    //递归(如何实现?)
    //    List<String> res = new ArrayList<>();
    //    binaryTreePaths(root, "", res);
    //    return res;
    //}
    //
    ////root:树
    ////path:当前树根节点 带的路径
    ////res 路径,每一个元素都是一个根节点到叶子节点的路径
    //public void binaryTreePaths(TreeNode root, String path, List<String> res) {
    //    if (root == null) {
    //        return;
    //    } else {
    //        path = path + root.val;//3->7->root.val
    //        if (root.left == null && root.right == null) {
    //            //说明叶子节点
    //            res.add(path);
    //        } else {
    //            //说明要递归:把->加入
    //            path = path + "->";
    //            //递归左
    //            binaryTreePaths(root.left, path, res);
    //            //递归右
    //            binaryTreePaths(root.right, path, res);
    //        }
    //    }
    //}
